package Algorithm.Sort;

import java.util.Arrays;

public class BinaryInsertSort {
    // 二分插入排序（折半插入排序）
    // 在有序区间使用二分法选择数据应该插入的位置时，因为区间的有序性，可以利用二分查找（折半查找）的思想
    public static void binaryInsertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int right = i;
            int left = 0;
            int val = arr[i];
            while (left < right) {
                int mid = left + ((right - left) >> 1);
                if (val < arr[mid]) {
                    right = mid;
                } else {
                    // val >= arr[mid]
                    left = mid + 1;
                }
            }
            if (i - left >= 0) System.arraycopy(arr, left, arr, left + 1, i - left);
            // left就是val插入的位置
            arr[left] = val;
        }
    }
String re = "";
    public static void main(String[] args) {
        int[] arr = {2,1,5,3,7,2,8,4,9,6,3,10,4};
        binaryInsertSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
